package LeetCode;

public class No114 {
    public void flatten(TreeNode root) {
        //当前节点非空，如果左子节点非空，遍历左子树的最右端点，将左子树的最右端点的右子节点指针指向当前节点的右子节点，将当前节点的右子节点指向左孩子，左子节点指针置为空，访问当前节点的右子节点
        TreeNode curr = root;
        while(curr!=null){
            if(curr.left!=null){
                TreeNode next = curr.left;
                TreeNode pre = next;
                while(pre.right!=null){
                    pre=pre.right;
                }
                pre.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }

//          利用栈，将根节点压入栈底，取出栈顶元素，如果前置节点非空，就把出栈的这个元素放到前置节点的右子节点上，然后先把当前节点的右孩子压入栈
        //  再把左孩子压入栈，最后把当前节点赋值给前置节点
//        Deque<TreeNode> stack = new LinkedList<>();
//        TreeNode prenode = null;
//        stack.push(root);
//        while(stack.size()!=0){
//            TreeNode curr = stack.pop();
//            if(prenode!=null){
//                prenode.left = null;
//                prenode.right = curr;
//            }
//            if(curr.right!=null) stack.push(curr.right);
//            if(curr.left!=null) stack.push(root.left);
//            prenode = curr;
//        }
    }

}
